package com.cet.qz.unit01.chapter1_3;

import java.util.Iterator;

/**
 * @program: algorithm
 * @description: 链表实现环形队列
 * @author: 陈恩涛
 * @create: 2021-04-16 21:41
 **/
public class Qz1_3_29 {
    public static void main(String[] args) {
        CircleQueue<Integer> cq = new CircleQueue<>();
        cq.enqueue(1);
        cq.enqueue(2);
        cq.enqueue(3);
        for (Integer integer : cq) {
            System.out.println(integer);
        }
    }

}

class CircleQueue<Item> implements Iterable<Item> {

    private class Node {
        private Item item;
        private Node next;
    }

    // 这里只是用一个实例变量last，因为first == last.next
    private Node last; //队列尾节点

    private int n;

    public boolean isEmpty() {
        return last == null;
    }

    public int size() {
        return n;
    }

    public void enqueue(Item item) {
        Node node = new Node();
        node.item = item;
        if (isEmpty()) {
            last = node;
            node.next = last;
        } else {
            node.next = last.next;
            last.next = node;
            last = node;
        }
        n++;
    }

    public Item dequeue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空！");
        }

        Item item = last.next.item;
        if (last.next == last) {
            last = null;
        } else {
            last.next = last.next.next;
        }
        n--;
        return item;
    }

    @Override
    public Iterator<Item> iterator() {
        return new CircleIterator(last);
    }

    class CircleIterator implements Iterator<Item> {

        private Node lastNode;

        public CircleIterator(Node lastNode) {
            this.lastNode = lastNode;
        }

        @Override
        public boolean hasNext() {
            return lastNode != null;
        }

        @Override
        public Item next() {
            Item item = lastNode.next.item;
            if (lastNode.next == lastNode) {
                //这里呼应hasNext方法，注意细节
                lastNode = null;
            } else {
                lastNode.next = last.next.next;
            }
            return item;
        }

        @Override
        public void remove() {

        }
    }
}

